1. Field of the Invention
The present invention relates to techniques of providing and evaluating a proof system performing proof and verification by a plurality of parties communicating with one another. In particular, the present invention relates to an evaluation method and system for a proof system in which, if a party performs communication in accordance with a predetermined protocol, then it is ensured that secret information is not leaked from the party to another party.
2. Description of the Related Art
In cryptographic technologies employed in, for example, secret key system, electronic signature, and authentication, it is necessary for cryptography protocols to prevent leakage of secret information such as a secret key or a password. There has been known a method for proving whether a cryptography protocol has the property of concealing secret information. An example of such a proving method is to determine whether the cryptography protocol is included in a zero-knowledge proof class.
In this specification, the zero-knowledge proof class is defined as a subset which forms part of a set of interactive proof protocols for proving something by communicating between a prover having secret information and a verifier to verify that the prover has indeed the secret information, the subset having interactive proof protocols allowing the proofs to yield nothing beyond the validity of the prover having the secret information.
A general zero-knowledge proof system will be described hereinafter. For reference purposes, details of zero-knowledge proof systems are described in Japanese Patent Application Unexamined Publication No. 2001-251289 (pp. 12-29, FIG. 1), Okamoto et al. Sangyo Tosyo Shuppan, “Modern cryptography” Jul. 30, 1997, pp. 131-150, and Oded Goldreich, Cambridge, “Foundation of Cryptography” 2001 pp. 184-330.
Zero-Knowledge Proof Systems
Consider a general case where a proof system is composed of a prover P and a verifier V, which interact with one another so that the verifier V verifies the validity of a proof that the prover P has a witness W. Hereafter, if R(X, W)=1 is satisfied, then it is described as (X, W).epsilon.R, where X is common input supplied to both the prover P and the verifier V, W is the witness of X, which is known by the prover P (typically secret information), and R( ) is a function. Assuming that
(X, W) ∈ R has the following property:
                Given X, W and R( ), it is easy to computationally determine whether (X, W) ∈ R is satisfied; and        Given only X and R( ), it is substantially impossible to determine the information W satisfying (X, W) ∈ R.A typical example of such (X, W) ∈ R is included in a discrete logarithm problem. Assuming that X={p, g, h}, W={w}, p is a large prime, g is an element of reduced residue class group (Z/pZ)*, w is an element of residue class group Z/(p−1)Z, and h=gW mod p, if an equation h=gW (mod p) is satisfied, then X and W meet the relationship R. In this example, when W is given, it is easy to determine whether h=gw (mod p) is satisfied. However, it is substantially impossible to determine w from X because an extremely large number of multiplications on modulo p are needed. For example, in the case of p is a 1024-bit prime number, the multiplication computation is repeated 21013 times to obtain W from X but only 210 times to determine whether (X, W) ∈ R is satisfied.        
An example of the zero-knowledge proof system in the case of (X, W) ∈ R will be described briefly hereinafter.
Step 1: the verifier V generates random numbers b and c ∈ Z/(p−1)Z from its own random tape and calculates A=gbhc mod p, which is sent to the prover P.
Step 2: the prover P generates s ∈ Z/(p−1)Z from its own random tape and calculates B=gs mod p, which is sent to the verifier V.
Step 3: the verifier V sends b and c, which are used for generation of A in the step (1), to the prover P.
Step 4: the prover P determines whether A=gbhc mod p is satisfied. If not satisfied, it is determined that the verifier V incorrectly operates, then the process is terminated. If satisfied, the prover P generates r=cw+s mod p−1 and sends it to the verifier V.
Step 5: the verifier V determines whether gr=hcB (mod p) is satisfied. If satisfied, the verifier V determines that the prover P knows the information w and outputs Acceptance. If not satisfied, the verifier V outputs Denial.
It is known that the above-described zero-knowledge proof system satisfies the following properties:                Property 1: If the prover P knows w and the prover P and the verifier V correctly perform the above-described steps, then the verifier V outputs Acceptance. Since gr=gcw+s (mod p)=gwcgs=hcB (mod p), Property (1) is apparently satisfied.        Property 2: If the prover P does not know w, then it is impossible for the prover to cause the verifier V to output Acceptance. The prover P knows c after g, h and B have been determined. Therefore, w is indispensable to calculate r satisfying gr=hcB (mod p) even if every c is received. If the protocol satisfies Property (1) and Property (2), then it is a zero-knowledge proof system.        Property 3: The verifier V cannot obtain any information related to w. The verifier V can obtain only A, B, b, c, and r in addition to its own random tape and p, g and h, which are previously given. If these data A, B, b, c, r and the random tape of the verifier V can be generated without communicating with the prover P, it can be said that the verifier V has no knowledge obtained from the prover P through the protocol.        
A general description of the zero-knowledge proof will be provided. Assuming a sequence of interactive data between the prover P and the verifier V in the order presented as follows: m1, m′1, m2, m′2, . . . , mk, m′k, where m1, m2, . . . , mk denote data transferred from the verifier V to the prover P, and m′1, m′2, . . . , m′k denote data transferred from the prover P to the verifier V. In addition, random tapes rV and rP are supplied to the verifier V and the prover P, respectively.
When the random tapes rV and rP are determined for fixed X and W, the sequence of interactive data m1, m′1, m2, m′2, . . . , mk, m′k, is obtained. Consider the distributing of m1, m′1, m2, m′2, . . . , mk, m′k, rV for the fixed X and W and the random tapes rP and rV chosen uniformly and randomly, wherein the distribution of the random tapes rV may be freely determined. The distribution of m1, m′1, m2, m′2, . . . , mk, m′k, rV is normally generated by the verifier V interacting with the prover P having the fixed W on the fixed X.
Now, it is assumed that there exists a simulator S which is supplied with a random tape rS and a sequence of interactive data n1, n′1, n2, n′2, . . . , nk, n′k, is generated for the fixed X and W by the verifier V interacting with the simulator S without any interaction with the prover P. Consider the distribution of n1, n′1, n2, n′2, . . . , nk, n′k, rV for the fixed X and W and the random tapes rS and rV chosen uniformly and randomly.
If the above-described two distributions: 1) the distribution of m1, m′1, m2, m′2, . . . , mk, m′k, rV for the fixed X and W and the random tapes rP and rV chosen uniformly and randomly; and 2) the distribution of n1, n′1, n2, n′2, . . . , nk, n′k, rV for the fixed X and W and the random tapes rS and rV chosen uniformly and randomly, are indistinguishable, then it is determined that the above-described interactive proof system is included in the zero-knowledge proof class. Since a sequence of data m1, m′1, m2, m′2, . . . , mk, m′k, rV after interacting with the prover P and a sequence of data n1, n′1, n2, n′2, . . . , nk, n′k, rV without interacting with the prover P are identically distributed, the verifier V cannot obtain any additional information.
To determine whether the two distributions are indistinguishable, the following method is used. A distinguisher D is provided to distinguish the two distributions (1) and (2), which is supplied with a random tape rD, a sequence of data m1, m′1, m2, m′2, . . . , mk, m′k, rV and a sequence of data n1, n′1, n2, n′2, . . . , nk, n′k, rV, and outputs 1 or 0 corresponding to True or Simulated as a result of distinguishment.
When rP, rV, and rD are chosen uniformly and randomly from predetermined distributions and the sequence of data m1, m′1, m2, m′2, . . . , mk, m′k, rV is supplied, the probability of the distinguisher D outputting 1 is denoted by:Pr—{rP, rV, rD}[D(m1, m′1, m2, m′2, . . . , mk, m′k, rV)=1].
When rS and rD are chosen uniformly and randomly from predetermined distributions and the sequence of data n1, n′1, n2, n′2, . . . , nk, n′k, rV is supplied, the probability of the distinguisher D outputting 1 is denoted by:Pr—{rS, rD}[D(n1, n′1, n2, n′2, . . . , nk, n′k, rV)=1)].
If for every distinguisher D the difference between Pr_{rP, rV, rD}[D(m1, m′1, m2, m′2, . . . , mk, m′k, rV)=1] and Pr_{rS, rD}[D(n1, n′1, n2, n′2, . . . , nk, n′k, rV)=1] is negligible, the two distributions are indistinguishable.
As described above, in order to include a proof system in the zero-knowledge proof class, it is necessary that the simulated data sequence generated by the simulator S and the true data sequence are indistinguishable for every distinguisher D for the fixed X and W. Since the condition is “every distinguisher D for the fixed X and W”, the distinguisher D includes a distinguisher having data w or information related to X and W, which is not known even by the prover P. Accordingly, the constraint required for the zero-knowledge proof class is very strict. It may be possible that the verifier happens to hit the information W. However, in the case of X and W uniformly and randomly generated from a random tape, it is substantially impossible for the verifier to know the information W for a very large number of random tapes but the information W may be known with a negligible small probability. Therefore, it is reasonable to study whether the information W may be leaked to the verifier in the case of X and W uniformly and randomly generated from a very large number of random tapes.
Honest-Verifier Zero-Knowledge
The case as described above is the zero-knowledge class for preventing leakage of information W for every malicious verifier. However, it is useful to consider an honest-verifier zero-knowledge class, especially when the verifier V sends only random numbers to the prover P.
Taking the discrete logarithm problem as an example, consider the case where the common input X is supplied to both of the prover P and the verifier V and the witness W of the common input X is supplied to only the prover P. It is assumed that X={p, g, h}, W={w}, p is a large prime, g is an element of reduced residue class group (Z/pZ)*, w is an element of residue class group Z/(p−1)Z, and h=gw mod p, if an equation h=gw (mod p) is satisfied, then X and W meet the relationship R. In the case of the every-verifier zero-knowledge class, the verifier V generates random numbers b and c ∈ Z/(p−1)Z and calculates A=gbhc mod p to output A to the prover P. Thereafter, the prover P generates s ∈ Z/(p−1)Z from the random tape thereof and calculates B=gs mod p to the verifier V. Since the prover P sends B to the verifier v after the verifier V has sent A to the prover P, the random number c cannot be intentionally selected by the verifier V depending on B. However, in the case of the honest-verifier zero-knowledge class, the verifier V selects the random number c uniformly and randomly and therefore the protocol can be simplified as follows:                1) The prover P generates s ∈ Z/(p−1)Z from the random tape thereof and calculates B=gs mod p to the verifier V.        2) The verifier V selects c uniformly and randomly and sends it to the prover P.        3) The prover P calculates r=cw+s mod p−1 to send it to the verifier V.        4) The verifier V determines whether the equation: gr=hcB (mod p) is satisfied. If satisfied, then the verifier V determines that the prover P indeed knows the witness w and therefore outputs Acceptance. If not satisfied, then the verifier V outputs Denial.        
In the case of the honest-verifier zero-knowledge class, the simulator S creates c and r uniformly and randomly and sends B=grh−c mod p to the verifier V. The above-described simplification has an advantage more than expected. It is essential that the verifier V inputs B before selecting c randomly.
Application to Hash Function
Application of the zero-knowledge class to the hash function Hash( ) may achieve the similar security as described above by the prover V itself generating c=Hash(B, p, g, h) instead of the verifier V. A protocol introducing the hash function is as follows:    1) The prover P generates s ∈ Z/(p−1)Z from the random tape thereof and calculatesB=gs mod p,C=Hash(p, g, h, B), andr=cw+s mod p−1;    2) The prover P sends B and r to the verifier V; and    3) The verifier V calculates c′=Hash (p, g, h, B) and determines whether the equation: gr=hc′B (mod p) is satisfied. If satisfied, then the verifier V determines that the prover P indeed knows the witness w and therefore outputs Acceptance. If not satisfied, then the verifier V outputs Denial.
In this manner, this modified system has no need of sending data from the verifier V to the prover P. Accordingly, after the prover P has sent B and r to the verifier V, anyone can verify its validity. This can be applied to digital signature, encryption system or the like. Taking a digital signature as an example, a text M is reduced to an element g of (Z/pZ)* by using Hash function, g=Hash (M). Note that this hash function g=Hash (M) does not directly relate to the zero-knowledge proof. Subsequently, h=gw mod p is used to generate B and r for zero-knowledge proof and the text M is attached with h, B and r. A signature verifier reproduces g from M and c from p, h, g and B to determined whether an equation: gr=hc′B (mod p) i satisfied.
As described above, it is possible to prove arbitrary interactively-provable thing by using an interactive proof protocol included in the zero-knowledge proof class. However, such zero-knowledge interactive proof protocols do not always provide effective proof systems. Actually, it is very frequently difficult to design effective proof systems.